package java0329;

class TreeNode {
    public int key;
    public int value;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

public class BinarySearchTree {
    private TreeNode root = null;

    // 根据 key 的值查找 value
    public Integer get(int key) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.key > key) {
                cur = cur.left;
            }else if (cur.key < key) {
                cur = cur.right;
            }else {
                return cur.value;
            }
        }
        return null;
    }

    // 根据 key 的值查找 value
    // 如果查找不到，返回默认值
    public Integer getOrDefault(int key, int defaultVal) {
        Integer ret = get(key);
        if (ret == null) {
            return defaultVal;
        }
        return ret;
    }

    // 插入新的键值对
    public void put(int key, int value) {
        // 为空树的时候，直接将这个键值对变为 root 节点
        if (root == null) {
            root = new TreeNode(key, value);
            return;
        }
        TreeNode cur = root;
        TreeNode pre = null;
        while (cur != null) {
            if (key > cur.key) {
                pre = cur;
                cur = cur.right;
            }else if (key < cur.key) {
                pre = cur;
                cur = cur.left;
            }else {
                cur.value = value;
                return;
            }
        }
        if (pre.key > key) {
            pre.left = new TreeNode(key, value);
        }
        if (pre.key < key) {
            pre.right = new TreeNode(key, value);
        }
        return;
    }

    // 根据 key 的值删除对应的键值对
    public void remove(int key) {
    }
}
